import java.util.Random;

public class SortMerge {
    /**
     * 归并排序
     */
    public static void MergeSort(int[] array) {
        if (array == null || array.length < 2) return;
        MergeSortCore(array, 0, array.length - 1);
    }

    //递归
    public static void MergeSortCore(int[] array, int lo, int hi) {
        if (lo == hi) return;                   //退出递归
        int mid = lo + ((hi - lo) >> 1);
        MergeSortCore(array, lo, mid);          //左排序
        MergeSortCore(array, mid + 1, hi);  //右排序
        Merge(array, lo, mid, hi);              //二路归并
    }

    //二路归并
    public static void Merge(int[] array, int lo, int mid, int hi) {
        int[] temp = new int[hi - lo + 1];
        int i = 0, p1 = lo, p2 = mid + 1;
        while (p1 <= mid && p2 <= hi) {
            temp[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
        }
        while (p1 <= mid) {
            temp[i++] = array[p1++];
        }
        while (p2 <= hi) {
            temp[i++] = array[p2++];
        }
        for (i = 0; i < temp.length; i++) {
            array[lo + i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[]arr = new int[10000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Random().nextInt();
        }
        long start = System.currentTimeMillis();
        MergeSort(arr);
        long end = System.currentTimeMillis();
        System.out.println("MergeSort花费了：" + (end-start) + "ms");
        start = System.currentTimeMillis();
        SortQuick.QuickSort(arr);
        end = System.currentTimeMillis();
        System.out.println("QuickSort花费了：" + (end-start) + "ms");
    }
}
